package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 例如：[2,5,1,4,3]这个数组中，逆序对有[2,1][5,1][5,3][5,4][4,3]
 * 求一个数组中有多少个逆序对
 */
public class T08_逆序对个数_归并排序法 {
    //归并过程中要用到的临时数组
    private static int[] helper = null;
    //逆序对个数统计
    private static int reversePair = 0;

    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(6, 0, 20);
        helper = new int[arr.length];
        ArrayUtil.print(arr);
        int result = solution(arr);
        System.out.println("result = " + result);
    }

    private static int solution(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
        ArrayUtil.print(arr);
        return reversePair;
    }

    private static void mergeSort(int[] arr, int p, int r) {
        if (p < r) {
            int mid = p + (r - p) / 2;
            mergeSort(arr, p, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, p, mid, r);
        }
    }

    private static void merge(int[] arr, int p, int mid, int r) {
        System.arraycopy(arr, p, helper, p, r - p + 1);
        int left = p;
        int right = mid + 1;
        int current = p;

        while (left <= mid && right <= r) {
            if (helper[left] <= helper[right]) {
                arr[current++] = helper[left++];
            } else {
                arr[current++] = helper[right];
                //只要右侧区域当前待排序元素比左侧的当前待排序元素小，则一定存在逆序对，且一定比所有左侧待排序元素都小
                reversePair += mid - left + 1;
                for (int i = left; i <= mid; i++) {
                    System.out.println("逆序对:(" + helper[i] + "," + helper[right] + ")");
                }
                right++;
            }
        }
        while (left <= mid){
            arr[current++] = helper[left++];
        }
        while (right <= r){
            arr[current++] = helper[right++];
        }
    }
}
